package com.trajan.exercise.datastructure;

/*

   Created with IntelliJ IDEA.

   Ing. Tomáš Herich
   --------------------------- 
   14. 06. 2013
   10:25 AM

*/

public class LinkedList {

    private Node firstNode;
    private Node lastNode;

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        for (int i = 0; i < 10; i++) {
            list.addNode(i);
        }

        // Traverse
        //list.inOrderTraverse();

        // Get node
        int getNodeId = 2;
        Node node = list.getNode(getNodeId);
        if (node != null) {
            System.out.println("\nGet node id" + getNodeId + ": " + node.toString());
        } else {
            System.out.println("\nGet node id" + getNodeId + ": " + "null");
        }

        // Size
        System.out.println("\nList size is: " + list.getSize());


        // Remove node
        list.removeNode(list.getNode(3));
        list.inOrderTraverse();

        // Size
        System.out.println("\nList size is: " + list.getSize());


        // Loop detection by checking all previous nodes
//        long startTime = System.currentTimeMillis();
//
//        System.out.println("\nHas loop: " + list.hasLoop());
//        list.getNode(5).setNextNode(list.getNode(1));
//        System.out.println("\nHas loop: " + list.hasLoop());
//
//        long endTime = System.currentTimeMillis();
//        System.out.println("Duration: " + (endTime - startTime) + " ms");

        // Loop detection by Floyd's algorithm
        long startTime = System.currentTimeMillis();

        System.out.println("\nHas loop: " + list.hasLoopFloyd());
        list.getNode(5).setNextNode(list.getNode(1));
        System.out.println("\nHas loop: " + list.hasLoopFloyd());

        long endTime = System.currentTimeMillis();
        System.out.println("Duration: " + (endTime - startTime) + " ms");

        //list.inOrderTraverse();

    }

    public boolean hasLoopFloyd() {

        Node selectedNodeFast, selectedNodeSlow;
        selectedNodeFast = selectedNodeSlow = firstNode;

        while(selectedNodeFast != null && selectedNodeSlow != null) {

            if (selectedNodeFast.getNextNode() != null) {
                selectedNodeFast = selectedNodeFast.getNextNode().getNextNode();
            } else {
                return false;
            }

            selectedNodeSlow = selectedNodeSlow.getNextNode();

            if (selectedNodeFast == selectedNodeSlow) {
                return true;
            }
        }

        return false;
    }

    public boolean hasLoop() {

        int selectedNodeIndex = 0;
        Node selectedNode = firstNode;

        while (selectedNode != null) {

            selectedNode = selectedNode.getNextNode();
            selectedNodeIndex++;

            if (selectedNode != null) {

                System.out.println("selected ndoe index: " + selectedNodeIndex);
                for (int i = 0; i < selectedNodeIndex; i++) {

                    Node test = getNode(i);

                    if (test.equals(selectedNode)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public Node getNode(int nodeId) {

        int nodeCounter = 0;

        Node selectedNode = firstNode;

        while (selectedNode != null) {

            if (nodeCounter == nodeId) {
                return selectedNode;
            } else {
                selectedNode = selectedNode.getNextNode();
                nodeCounter++;
            }
        }

        return null;
    }

    public int getSize() {

        int counter = 0;
        Node selectedNode = firstNode;

        while (selectedNode != null) {

            selectedNode = selectedNode.getNextNode();
            counter++;

        }

        return counter;
    }


    public void inOrderTraverse() {

        Node selectedNode = firstNode;

        while (selectedNode != null) {

            System.out.println(selectedNode.toString());

            selectedNode = selectedNode.getNextNode();

        }
    }

    public void addNode(Object value) {

        Node node = new Node(value);

        if (lastNode == null) {
            firstNode = node;
            lastNode = node;
        } else {

            lastNode.setNextNode(node);
            lastNode = node;
        }

    }

    public void removeNode(Node node) {

        if (node == firstNode) {
            firstNode = firstNode.getNextNode();
            return;
        }

        Node selectedNode, previousNode;
        selectedNode = firstNode;

        while (selectedNode != null) {

            previousNode = selectedNode;

            selectedNode = selectedNode.getNextNode();

            if (selectedNode == node) {

                previousNode.setNextNode(selectedNode.getNextNode());

            }
        }
    }

    public class Node {

        Node nextNode;
        Object value;

        private Node(Object value) {
            this.value = value;
        }

        public void setNextNode(Node node) {
            nextNode = node;
        }

        public Node getNextNode() {
            return nextNode;
        }

        @Override
        public String toString() {
            return "Node with value: " + value.toString();
        }
    }

}
